package algorithm.swordoff;

import java.util.*;

/**
 * 字符串的排列
 *
 * permutation使用hashset去除重复字符串
 * permutation2在展开树中剪枝去除重复
 *
 */

public class SQ38 {

    public String[] permutation(String s) {
        char[] split = s.toCharArray();
        boolean[] isUsed = new boolean[split.length];
        Set<String> ans = new HashSet<>();
        permute(split, ans, split.length, isUsed, new StringBuilder(""));
        return ans.toArray(new String[0]);
    }

    public void permute(char[] availableCharArray,
                        Set<String> ans,
                        int targetSize,
                        boolean[] isUsed,
                        StringBuilder current) {

        if (current.length() == targetSize) ans.add(current.toString());

        for (int i = 0; i < availableCharArray.length; i++) {

            if (!isUsed[i]) {
                isUsed[i] = true;
                current.append(availableCharArray[i]);
                permute(availableCharArray, ans, targetSize, isUsed, current);
                isUsed[i] = false;
                current.deleteCharAt(current.length() - 1);
            }
        }
    }


    public String[] permutation2(String s) {
        char[] split = s.toCharArray();
        Arrays.sort(split);
        boolean[] isUsed = new boolean[split.length];
        List<String> ans = new LinkedList<>();
        permute2(split, ans, split.length, isUsed, new StringBuilder(""));
        return ans.toArray(new String[0]);
    }

    public void permute2(char[] availableCharArray,
                         List<String> ans,
                         int targetSize,
                         boolean[] isUsed,
                         StringBuilder current) {

        if (current.length() == targetSize) ans.add(current.toString());

        // 画个树状图就可以知道什么情况下剪枝了,例子可以是"aaab"
        // 上一轮用过的数字也就是在第一个T之前的F,如果和本轮T对应的char一样,就跳过,回溯展开的for循环保证了这个顺序
        int lastUsed = -1;
        for (int i = 0; i < availableCharArray.length; i++) {
            if (isUsed[i]) lastUsed = i;
            // 本轮尝试的是第一个char 或者 T前面最近的一个F对应的两个char不一样就向深层展开
            else if (lastUsed == -1 || availableCharArray[i] != availableCharArray[lastUsed]) {
                isUsed[i] = true;
                current.append(availableCharArray[i]);
                permute2(availableCharArray, ans, targetSize, isUsed, current);
                isUsed[i] = false;
                current.deleteCharAt(current.length() - 1);
            }
        }
    }



    public static void main(String[] args) {
        SQ38 sq38 = new SQ38();
        System.out.println(Arrays.toString(sq38.permutation("aaab")));
        System.out.println(Arrays.toString(sq38.permutation2("aaab")));
    }

}
